package com.剑指offer;

import java.util.LinkedList;
import java.util.Queue;

public class _奇安信
{

}

//幸运编号

//class Node{
//    int data;
//    Node next;
//    public Node(int data) {
//        this.data=data;
//    }
//}
//public class Main {
//
//    public static int selution(int N) {
//        int result = 0;
//        //循环链表创建
//        Node head = new Node(1);
//        Node temp = head;
//        for(int i = 2;i <= N;i++) {
//            temp.next = new Node(i);
//            temp = temp.next;
//        }
//        //temp 初值指向队尾的元素
//        temp.next = head;
//        while(true) {
//            for(int i=0;i < 4;i++) {//为了易于删除，只遍历到第四个元素即可
//                temp = temp.next;
//            }
//            if(temp.next.data != N) {//判断第五个元素是否为队尾元素
//                temp.next=temp.next.next;
//                result++;
//            }else {
//                return ++result;
//            }
//        }
//    }
//}







/**
 * 奇安信笔试第一题: 线程树
 * 第一题给的题目意思是输入两个数组，第一个数组是子线程（子节点），
 * 第二个数组是父线程（父节点），删除一个线程会删除此线程的所有子线程，问给出一个要删除的线程，总共要删除掉几个线程？
 *
 * 利用队列就可以解决
 */
//import java.util.LinkedList;
//        import java.util.Queue;
//        import java.util.Scanner;
//public class Main {
//    public static void main(String[] args) {
//        //处理输入数据
//        Scanner scanner = new Scanner(System.in);
//        String a = scanner.nextLine();
//        String b = scanner.nextLine();
//        int temp = scanner.nextInt();
//        String[] s1 = a.split(" ");
//        int[] kids = new int[s1.length];
//        for (int i = 0; i < s1.length; i++) {
//            kids[i] = Integer.parseInt(s1[i]);
//        }
//        String[] s2 = b.split(" ");
//        int[] parents = new int[s2.length];
//        for (int i = 0; i < s2.length; i++) {
//            parents[i] = Integer.parseInt(s2[i]);
//        }
//        scanner.close();
//
//        //定义队列存储关联节点
//        Queue<Integer> queue = new LinkedList<>();
//        queue.offer(temp);
//        //结果值
//        int count = 0;
//        //标志符
//        boolean flag = false;
//
//        //如果输入的目标线程temp值为0，count--，没有为0的线程
//        if (temp == 0)
//            count--;
//        //判断输入的目标线程temp值在不在kids数组中
//        for (int i = 0; i < kids.length; i++) {
//            if (kids[i] == temp) {
//                flag = true;
//                break;
//            }
//        }
//        if (!flag)
//            System.out.println(0);
//        //队列处理操作
//        while (!queue.isEmpty()){
//            temp = queue.poll();
//            for (int i = 0; i < kids.length; i++) {
//                if (parents[i] == temp && kids[i] != 0){
//                    queue.offer(kids[i]);
//                }
//            }
//            count++;
//        }
//
//        System.out.println(count);
//    }
//}








//二叉树的公共祖先

//奇安信集团 2020校招 服务端开发-应用开发方向在线考试
//        编程题|20分2/2
//        寻祖问宗
//        时间限制：C/C++语言 1000MS；其他语言 3000MS
//        内存限制：C/C++语言 65536KB；其他语言 589824KB
//        题目描述：
//        姓氏是人的符号标志，是家族血脉的传承；族谱是家族血脉传承的文字记载。同姓的两个中国人，
// 根据族谱或许能够查出上面几代内是同一个祖先。查一下族谱，也许当代某位同姓名人就是你的远房亲戚，惊喜不惊喜，意外不意外！！！
//
//
//
//        输入
//        二元查找树（1.若左子树不空，左子树值都小于父节点；2.如右子树不空，右子树值都大于父节点；
// 3.左、右子树都是二元查找树；4. 没有键值相等的节点）上任意两个节点的值，请找出它们最近的公共祖先。
//
//        输入三行行，第一行为树层级，第二行为数节点（其中-1表示为空节点），第三行为需要查找祖先的两个数。
//
//        在例图中（虚线框没有真实节点，为了输入方便对应位置输-1）查找12和20的最近公共祖先输入为：
//        9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
//        20
//
//
//        输出
//        输出给出两个数在树上的最近公共祖先数值，如果没有公共祖先，输出-1；如果其中一个节点是另一个节点的祖先，
// 输出这个祖先点（如例图中找15、20最近公共祖先，输出15）；如果输入无效，输出-1。
//
//
//        样例输入
//        9 6 15 2 -1 12 25 -1 -1 -1 -1 -1 -1 20 37
//        20
//        样例输出
//import java.util.LinkedList;
//        import java.util.Scanner;
//
//public class Main{
//    static class TreeNode{
//        int value;
//        TreeNode left;
//        TreeNode right;
//        public TreeNode(int value){
//            this.value = value;
//        }
//    }
//    public static TreeNode root;
//    public static TreeNode p;
//    public static TreeNode q;
//    public static TreeNode commonfather;
//    public static void main(String[] args) {
//
//        /***********************层次创建二叉树***********************/
//        Scanner sc = new Scanner(System.in);
//        int depth = sc.nextInt();
//        sc.nextLine();
//        String[] array1 = sc.nextLine().trim().split(" ");
//        int pval = sc.nextInt();
//        int qval = sc.nextInt();
//        int len = array1.length;
//        int[] intlevelarray = new int[len];
//        for (int i = 0; i < len; i++) {
//            intlevelarray[i] = Integer.valueOf(array1[i]);
//        }
//        root = level_buildBTree(intlevelarray,-1,pval,qval);
//        boolean result = recurseTree(root, p, q);
//        if(result && commonfather!=null){
//            System.out.println(commonfather.value);
//        }else{
//            System.out.println(-1);
//        }
//
//
//    }
//    /**层次遍历创建二叉树*/
//    public static TreeNode level_buildBTree(int[]array,int flag, int pval, int qval){
//        int len = array.length;
//        //将数组转成list
//        LinkedList<TreeNode> list = new LinkedList<>();
//        for (int i = 0; i < len; i++) {
//            TreeNode temp = new TreeNode(array[i]);
//            if(array[i]==pval){
//                p = temp;
//            }
//            if(array[i]==qval){
//                q = temp;
//            }
//            list.add(temp);
//        }
//        //开始构建树
//        for (int i = 0; i < len/2; i++) {
//            list.get(i).left = list.get(2*i+1).value!=flag?list.get(2*i+1):null;
//            //记得处理最后一个父节点（len/2-1），因为有可能没有右孩子。
//            if(i<len/2-1 ||(i==len/2-1&& len%2!=0)){
//                list.get(i).right = list.get(2*i+2).value!=flag?list.get(2*i+2):null;
//            }
//        }
//        return list.get(0);
//    }
//
//    /**
//     * 二叉树的最近公共祖先
//     * @param currNode 当前节点
//     * @param p 第一个孩子
//     * @param q    第二个孩子
//     * @return
//     */
//    public static boolean recurseTree(TreeNode currNode, TreeNode p, TreeNode q){
//        if(currNode == null){
//            return false;
//        }
//        int left = recurseTree(currNode.left, p, q)?1:0;
//        int right = recurseTree(currNode.right, p, q)?1:0;
//        int mid = (currNode==p || currNode==q)?1:0;
//        if(mid+left+right>=2){
//            commonfather = currNode;
//        }
//        return mid+left+right>0;
//    }
//}
